package top.retain;

import java.util.Arrays;

/**
 * @author ivorfan
 * @date 2021/7/26 18:00
 */
public class minSubArrayLen {

    public static void main(String[] args) {
        minSubArrayLen(11,new int[] {
                1,2,3,4,5
        });
    }
    public static int minSubArrayLen(int target, int[] nums) {
        int n = nums.length;
        int[] sums = new int[n + 1];
        int minLength = Integer.MAX_VALUE;
        for (int i = 1;i<= n; i++) {
            sums[i] = sums[i-1] + nums[i - 1];
        }
        for (int i = 1;i <=n; i++) {
            // target 加上 前i-1个和，然后进行二分查找target，用于计算中间区间
            int newTarget  = target + sums[i - 1];
            int mid = Arrays.binarySearch(sums, newTarget);
            // 未找到
            if (mid < 0) {
                // 应插入的位置，左边比target小，右边比target大
                mid = ~mid;
            }
            // 找到target,区间长度：mid - (i-1); 即mid - i + 1。
            if (mid <= n)
                minLength = Math.min(minLength, mid - i + 1);
        }
        return minLength == Integer.MAX_VALUE ? 0 : minLength;
    }
}
